然后枚举因数暴力计算.
#include <cstdio>
#define LL long long
const int MAXN = 1 << 17;
LL n;
int prn , prime[ MAXN + 5 ];
bool vis[ MAXN + 5 ];
void sieve( ) {
for( int i = 2 ; i <= MAXN ; i ++ ) {
if( !vis[ i ] ) prime[ ++ prn ] = i;
for( int j = 1 ; j <= prn && 1ll * i * prime[ j ] <= MAXN ; j ++ ) {
vis[ i * prime[ j ] ] = 1;
if( i % prime[ j ] == 0 ) break;
}
}
}
LL phi( LL n ) {
LL Ans = n;
for( int i = 1 ; i <= prn ; i ++ ) {
if( n < prime[ i ] ) break;
if( n % prime[ i ] == 0 ) {
while( n % prime[ i ] == 0 ) n /= prime[ i ];
Ans = Ans / prime[ i ] * ( prime[ i ] - 1 );
}
}
if( n > 1 ) Ans = Ans / n * ( n - 1 );
return Ans;
}
LL f( LL n ) {
LL Ans = 0;
for( LL i = 1 ; i * i <= n ; i ++ )
if( n % i == 0 ) Ans += i * phi( n / i ) + ( i * i == n ? 0 : phi( i ) * ( n / i ) );
return Ans;
}
int main( ) {
sieve( );
scanf("%lld",&n);
printf("%lld\n", f( n ) );
return 0;
}
